/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution309 {

    public static void main(String args[]) {
        Solution309 s = new Solution309();
        System.out.println(s.maxProfit(new int[]{1, 2, 10, 0, 2}));
    }

    static int CHI = 0;
    static int KMAI = 1;
    static int BMAI = 2;

    public int maxProfit(int[] prices) {

        int n = prices.length;
        if(n == 0){
            return 0;
        }
        int dp[][] = new int[n + 1][3];

        int p = prices[0];
        dp[0][CHI] = 0;
        dp[0][KMAI] = 0;
        dp[0][BMAI] = 0;

        for (int i = 1; i < n; i++) {
            if ((dp[i - 1][KMAI] + (p - prices[i])) > dp[i - 1][CHI]) {
                dp[i][CHI] = dp[i - 1][KMAI];
                p = prices[i];
            } else {
                dp[i][CHI] = dp[i - 1][CHI];
            }
            dp[i][KMAI] = max(dp[i - 1][KMAI], dp[i - 1][BMAI]);
            dp[i][BMAI] = max(0, dp[i - 1][CHI] + prices[i] - p);
        }
        return max(max(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
    }

    public int max(int a, int b) {
        return a > b ? a : b;
    }
}
